import java.util.ArrayList;
import java.util.List;

class Solution21 {
    public static List<String> ret;
    public static StringBuffer path;
    public static List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuffer();
        dfs(s,0);
        return ret;
    }

    public static void dfs(String s,int pos) {
        if(path.length() == s.length()) {
            ret.add(path.toString());
            return;
        }
        path.append(s.charAt(pos));
        dfs(s,pos+1);
        path.deleteCharAt(path.length()-1);
        if(s.charAt(pos) >= 'a' && s.charAt(pos) <= 'z') {
            char ch = (char)(s.charAt(pos)-32);
            path.append(ch);
            dfs(s,pos+1);
            path.deleteCharAt(path.length()-1);
        }else if(s.charAt(pos) >= 'A' && s.charAt(pos) <= 'Z') {
            char ch = (char)(s.charAt(pos)+32);
            path.append(ch);
            dfs(s,pos+1);
            path.deleteCharAt(path.length()-1);
        }
    }

    public static void main(String[] args) {
        List<String> ret = letterCasePermutation("a1b2");
        System.out.println(ret);
    }
}